/ Java Program to implement 
// Odd-Even / Brick Sort 

import java.io.*; 
  
class GFG { 
    public static void oddEvenSort(int arr[], int n) 
    { 
        boolean isSorted = false; // Initially array is unsorted 
  
        while (!isSorted) { 
            isSorted = true; 
            int temp = 0; 
  
            // Perform Bubble sort on odd indexed element 
            for (int i = 1; i <= n - 2; i = i + 2) { 
                if (arr[i] > arr[i + 1]) { 
                    temp = arr[i]; 
                    arr[i] = arr[i + 1]; 
                    arr[i + 1] = temp; 
                    isSorted = false; 
                } 
            } 
  
            // Perform Bubble sort on even indexed element 
            for (int i = 0; i <= n - 2; i = i + 2) { 
                if (arr[i] > arr[i + 1]) { 
                    temp = arr[i]; 
                    arr[i] = arr[i + 1]; 
                    arr[i + 1] = temp; 
                    isSorted = false; 
                } 
            } 
        } 
  
        return; 
    } 
    public static void main(String[] args) 
    { 
        int arr[] = { 34, 2, 10, -9 }; 
        int n = arr.length; 
  
        oddEvenSort(arr, n); 
        for (int i = 0; i < n; i++) 
            System.out.print(arr[i] + " "); 
  
        System.out.println(" "); 
    } 
} 
